Cable Guy (due Dec. 12^th)

There are N computers located in a rectangular office of size L x W, that is, a grid of L x W squares. The computers are placed in the center of squares. Coordinates (x_i, y_i) of all the computers are given. Your task is to connect the computers by laying cables on the ground and give the length of the cable connections. The computers should be connected by using the minimum length of cable such that each computer can send data to every other computer in the room. However, the cables can only be laid parallel to the walls, i.e., in horizontal and vertical directions only, and going through the center of all squares they cross (pass through). There can be more than one cable crossing a specific square but they can not be connected to each other. A computer can have any number of outgoing cables. Also, the office contains some square obstacles where cables should not pass such as tables, plants, cupboards, etc... You can see an example office with a minimum cable network connecting the computers, in the following figure:

Assumptions

1 £ N £ 100

1 £ L £ 200

1 £ W £ 200

0 £ x_i £ L-1

0 £ y_i £ W-1

The given numbers are all integers.

Input data is error-free, no need to check for correctness.

Input

The input file is named cable.inp. The first line of this file contains three integers, L, W and N respectively. In each the following N lines (ordered by computer number i = 0, 1, ..., N-1), there are two integers representing x_i and y_i, respectively. So, the 2nd line of the file corresponds to computer 0, the 3rd line corresponds to computer 1, and so on. The next line contains the number T of obstacle squares in the office. Each of the following T lines contains x and y coordinates of an obstacle square, respectively. The integers in the same line are separated by a single space.

Output

The output file is named cable.out. There should be only integers in the output file. The first line of this file should contain two integers representing the total length of cable used in the solution found in terms of square edges, and the number M of cable connections. Each of the following M lines should contain three integers separated by a space character. The first two integers should be the indices of a computer pair connected by a cable and the third one should be the length of the cable connecting them. The order of these M lines is not important. There may be more than one solution giving the same total cable length. You only need to give one of these solutions.

Example

(Hint: You can use breadth first search as a first step of your solution program.)

Regulations

Your source file should be named cable.c or cable.cpp. Your program should take no more than 10 seconds to run on Ineks 1-36. You will submit your homework as a single tar file using "submit315" command. Tar file must contain the following files

1. Makefile
2. cable.c[pp]
3. Other source code or user defined include files if any.

You can modify the sample Makefile given below to suit your needs. Use the command "make" to compile your program.

--- Makefile ---
all: cable
cable: cable.c
[TAB]g++ -Wall -O3 -o cable cable.c
--- End of Makefile ---

Please replace [TAB] with tab character.